/*
 Copyright (C) 2010 Kristian Duske

 Permission is hereby granted, free of charge, to any person obtaining a copy of this
 software and associated documentation files (the "Software"), to deal in the Software
 without restriction, including without limitation the rights to use, copy, modify, merge,
 publish, distribute, sublicense, and/or sell copies of the Software, and to permit
 persons to whom the Software is furnished to do so, subject to the following conditions:

 The above copyright notice and this permission notice shall be included in all copies or
 substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
 FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
 OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 DEALINGS IN THE SOFTWARE.
*/

#pragma once

#include "kd/collection_utils.h"

#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <memory>

// uncomment this to enable checking the invariant in debug builds
// #define KDL_SET_ADAPTER_DEBUG 1

namespace kdl
{
namespace detail
{

template <typename T, typename Allocator, typename Compare>
void sort_unique(std::vector<T, Allocator>& vec, const Compare& cmp)
{
  auto eq = [&cmp](const auto& lhs, const auto& rhs) {
    return !cmp(lhs, rhs) && !cmp(rhs, lhs);
  };
  std::sort(std::begin(vec), std::end(vec), cmp);
  vec.erase(std::unique(std::begin(vec), std::end(vec), eq), std::end(vec));
}

} // namespace detail

/**
 * Adapts a collection to the read only interface of std::set. The underlying collection
 * is expected to be sorted and it must not contain any pair of two values which are
 * equivalent according to the comparator used.
 *
 * If the given collection type is a reference, then this adapter will work directly on
 * the underlying collection. Otherwise, the collection will be copied by the constructor.
 *
 * In the former case, it must be ensured that the lifetime of this adapter does not
 * exceed the lifetime of the underlying collection.
 *
 * @tparam C the type of the underlying collection (this can be a reference)
 * @tparam Compare the type of the comparator to use for comparing the elements of the
 * underlying collection
 */
template <typename C, typename Compare = std::less<typename C::value_type>>
class const_set_adapter
{
protected:
  C m_data;

private:
  Compare m_cmp;

public:
  using key_type = typename std::remove_reference<C>::type::value_type;
  using value_type = key_type;
  using size_type = typename std::remove_reference<C>::type::size_type;
  using difference_type = typename std::remove_reference<C>::type::difference_type;
  using key_compare = Compare;
  using value_compare = Compare;
  using allocator_type = typename std::remove_reference<C>::type::allocator_type;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = typename std::allocator_traits<allocator_type>::pointer;
  using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
  using iterator = typename std::remove_reference<C>::type::iterator;
  using const_iterator = typename std::remove_reference<C>::type::const_iterator;
  using reverse_iterator = typename std::remove_reference<C>::type::reverse_iterator;
  using const_reverse_iterator =
    typename std::remove_reference<C>::type::const_reverse_iterator;

public:
  /**
   * Creates a set adapter using the given collection as its underlying collection. The
   * given collection must already be sorted and it must not contain any pair of two
   * equivalent values according to the given comparator.
   *
   * If the given collection type is a reference, then this adapter will work directly on
   * the underlying collection. Otherwise, the collection will be copied or moved by the
   * constructor.
   *
   * In the former case, it must be ensured that the lifetime of this adapter does not
   * exceed the lifetime of the underlying collection.
   *
   * @param data the collection
   * @param cmp the comparator
   */
  template <typename CC>
  explicit const_set_adapter(CC&& data, Compare cmp = {})
    : m_data{std::forward<CC>(data)}
    , m_cmp{std::move(cmp)}
  {
    assert(check_invariant());
  }

public:
  /**
   * Returns a copy of the allocator being used by the underlying vector.
   */
  allocator_type get_allocator() const { return m_data.get_allocator(); }
  /**
   * Returns a const iterator to the first element in the set. If the set is empty, the
   * returned iterator will be equal to cend().
   */
  const_iterator begin() const noexcept { return cbegin(); }

  /**
   * Returns a const iterator to the first element in the set. If the set is empty, the
   * returned iterator will be equal to cend().
   */
  const_iterator cbegin() const noexcept { return std::cbegin(m_data); }

  /**
   * Returns a const iterator to the element following the last element in the set
   * (past-the-end iterator).
   */
  const_iterator end() const noexcept { return cend(); }

  /**
   * Returns a const iterator to the element following the last element in the set
   * (past-the-end iterator).
   */
  const_iterator cend() const noexcept { return std::cend(m_data); }

  /**
   * Returns a const reverse iterator to the first element of the reversed set. If the
   * container is empty, the returned iterator will be equal to crend().
   */
  const_reverse_iterator rbegin() const noexcept { return crbegin(); }

  /**
   * Returns a const reverse iterator to the first element of the reversed set. If the
   * container is empty, the returned iterator will be equal to crend().
   */
  const_reverse_iterator crbegin() const noexcept { return std::crbegin(m_data); }

  /**
   * Returns a const reverse iterator to the element following the last element of the
   * reversed container.
   */
  const_reverse_iterator rend() const noexcept { return crend(); }

  /**
   * Returns a const reverse iterator to the element following the last element of the
   * reversed container.
   */
  const_reverse_iterator crend() const noexcept { return std::crend(m_data); }

  /**
   * Indicates whether this set is empty.
   *
   * @return true if this set is empty and false otherwise
   */
  bool empty() const noexcept { return m_data.empty(); }

  /**
   * Returns the number of values stored in this set.
   */
  size_type size() const noexcept { return m_data.size(); }

  /**
   * Returns the maximum possible number of values that can be stored in this set.
   */
  size_type max_size() const noexcept { return m_data.max_size(); }

  /**
   * Counts the number of values in this set which are equivalent to the given key.
   *
   * @tparam K the key type
   * @param x the key value
   * @return the number of values in this set which are equivalent to the given key
   */
  template <typename K>
  size_type count(const K& x) const
  {
    return find(x) != end() ? 1u : 0u;
  }

  /**
   * Finds the position of a value that is equivalent to the given key.
   *
   * @tparam K the key type
   * @param k the key
   * @return an iterator to a value that is equivalent to the given key, or end() if no
   * such value can be found
   */
  template <typename K>
  const_iterator find(const K& k) const
  {
    auto it = lower_bound(k);
    return it != end() && is_equivalent(k, *it) ? it : end();
  }

  /**
   * Returns a range of values which are equivalent to the given key.
   *
   * @tparam K the key type
   * @param x the key
   * @return a maximal range of equivalent values in this set
   */
  template <typename K>
  std::pair<const_iterator, const_iterator> equal_range(const K& x) const
  {
    return {lower_bound(x), upper_bound(x)};
  }

  /**
   * Returns the position of the greatest value that is less than or equal to the given
   * key, or end() if no such value can be found.
   *
   * @tparam K the key type
   * @param x the key
   * @return the position
   */
  template <typename K>
  const_iterator lower_bound(const K& x) const
  {
    return std::lower_bound(std::begin(m_data), std::end(m_data), x, key_comp());
  }

  /**
   * Returns the position of the smallest value that is greater than the given key, or
   * end() if no such value can be found.
   *
   * @tparam K the key type
   * @param x the key
   * @return the position
   */
  template <typename K>
  const_iterator upper_bound(const K& x) const
  {
    return std::upper_bound(std::begin(m_data), std::end(m_data), x, key_comp());
  }

  /**
   * Returns a copy of the comparator used to compare the keys. Returns the same
   * comparator as value_comp().
   */
  key_compare key_comp() const { return m_cmp; }

  /**
   * Returns a copy of the comparator used to compare the values. Returns the same
   * comparator as key_comp().
   */
  value_compare value_comp() const { return m_cmp; }

  /**
   * Returns the capacity of the underlying collection.
   */
  size_type capacity() const { return m_data.capacity(); }

  /**
   * Returns a const reference to the underlying collection.
   */
  const C& get_data() const { return m_data; }

  std::weak_ordering operator<=>(const const_set_adapter& other) const
  {
    const auto cmp = col_lexicographical_compare(m_data, other.m_data, key_comp());
    return cmp < 0   ? std::weak_ordering::less
           : cmp > 0 ? std::weak_ordering::greater
                     : std::weak_ordering::equivalent;
  }

  bool operator==(const const_set_adapter& other) const
  {
    return size() == other.size() && *this <=> other == 0;
  }

protected:
  bool check_invariant()
  {
#ifdef KDL_SET_ADAPTER_DEBUG
    if (empty() != (size() == 0u))
    {
      return false;
    }

    if (size() > 1u)
    {
      for (auto cur = begin(), last = std::prev(end()); cur != last; ++cur)
      {
        auto next = std::next(cur);
        if (!key_comp()(*cur, *next))
        {
          return false;
        }
      }
    }
#endif
    return true;
  }

  template <typename L, typename R>
  bool is_equivalent(const L& lhs, const R& rhs) const
  {
    return !key_comp()(lhs, rhs) && !key_comp()(rhs, lhs);
  }
};

/**
 * Adapts a collection to the full interface of std::set. The underlying collection is
 * expected to be sorted and it must not contain any pair of two values which are
 * equivalent according to the comparator used.
 *
 * If the given collection type is a reference, then this adapter will work directly on
 * the underlying collection. Otherwise, the collection will be copied by the constructor.
 *
 * In the former case, it must be ensured that the lifetime of this adapter does not
 * exceed the lifetime of the underlying collection.
 *
 * @tparam C the type of the underlying collection (this can be a reference)
 * @tparam Compare the type of the comparator to use for comparing the elements of the
 * underlying collection
 */
template <typename C, typename Compare = std::less<typename C::value_type>>
class set_adapter : public const_set_adapter<C, Compare>
{
private:
  using base = const_set_adapter<C, Compare>;

protected:
  using base::m_data;

public:
  using key_type = typename std::remove_reference<C>::type::value_type;
  using value_type = key_type;
  using size_type = typename std::remove_reference<C>::type::size_type;
  using difference_type = typename std::remove_reference<C>::type::difference_type;
  using key_compare = Compare;
  using value_compare = Compare;
  using allocator_type = typename std::remove_reference<C>::type::allocator_type;
  using reference = value_type&;
  using const_reference = const value_type&;
  using pointer = typename std::allocator_traits<allocator_type>::pointer;
  using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
  using iterator = typename std::remove_reference<C>::type::iterator;
  using const_iterator = typename std::remove_reference<C>::type::const_iterator;
  using reverse_iterator = typename std::remove_reference<C>::type::reverse_iterator;
  using const_reverse_iterator =
    typename std::remove_reference<C>::type::const_reverse_iterator;

public:
  using base::const_set_adapter;

  using base::get_allocator;

  using base::begin;
  using base::cbegin;

  using base::cend;
  using base::end;

  using base::crbegin;
  using base::rbegin;

  using base::crend;
  using base::rend;

  using base::empty;
  using base::max_size;
  using base::size;

  using base::count;

  using base::equal_range;
  using base::find;
  using base::lower_bound;
  using base::upper_bound;

  using base::key_comp;
  using base::value_comp;

  using base::capacity;
  using base::get_data;

public:
  /**
   * Assigns the values in the given initializer list to this set. The set is cleared and
   * the given values are inserted.
   *
   * @param values the values to insert
   * @return a reference to this set
   */
  set_adapter& operator=(std::initializer_list<value_type> values)
  {
    m_data = values;
    detail::sort_unique(m_data, key_comp());
    return *this;
  }

  /**
   * Returns an iterator to the first element in the set. If the set is empty, the
   * returned iterator will be equal to end().
   */
  iterator begin() noexcept { return std::begin(m_data); }

  /**
   * Returns an iterator to the element following the last element in the set
   * (past-the-end iterator).
   */
  iterator end() noexcept { return std::end(m_data); }

  /**
   * Returns a reverse iterator to the first element of the reversed set. If the container
   * is empty, the returned iterator will be equal to rend().
   */
  reverse_iterator rbegin() noexcept { return std::rbegin(m_data); }

  /**
   * Returns a reverse iterator to the element following the last element of the reversed
   * container.
   */
  reverse_iterator rend() noexcept { return std::rend(m_data); }

  /**
   * Clears all values from this set.
   *
   * Postcondition: empty()
   */
  void clear()
  {
    m_data.clear();
    assert(check_invariant());
  }

  /**
   * Increases capacity of the underlying vector.
   * All iterators may be invalidated.
   */
  void reserve(const size_t newCapacity)
  {
    m_data.reserve(newCapacity);
    assert(check_invariant());
  }

  /**
   * Inserts a copy of the given value into this set. If this set already contains a value
   * that is equivalent to the given value, nothing happens.
   *
   * If the given value could be inserted, then this function returns a pair of an
   * iterator to the inserted value and true, otherwise it returns a pair of an iterator
   * to the value that prevented insertion and false.
   *
   * Postcondition: this set contains a value equivalent to the given value and its size
   * has increased by one if the given value could be inserted
   *
   * @param value the value to insert
   * @return a pair of an iterator and a boolean that indicates whether the value was
   * inserted
   */
  std::pair<iterator, bool> insert(const value_type& value)
  {
    const auto result = do_insert(value);
    assert(check_invariant());
    return result;
  }

  /**
   * Inserts the given value into this set. If this set already contains a value that is
   * equivalent to the given value, nothing happens. If the value could be inserted, it
   * will have been moved into this set.
   *
   * If the given value could be inserted, then this function returns a pair of an
   * iterator to the inserted value and true, otherwise it returns a pair of an iterator
   * to the value that prevented insertion and false.
   *
   * Postcondition: this set contains a value equivalent to the given value and its size
   * has increased by one if the given value could be inserted
   *
   * @param value the value to insert
   * @return a pair of an iterator and a boolean that indicates whether the value was
   * inserted
   */
  std::pair<iterator, bool> insert(value_type&& value)
  {
    const auto result = do_insert(std::move(value));
    assert(check_invariant());
    return result;
  }

  /**
   * Inserts a copy of the given value using the given hint to speed up insertion. If the
   * given hint points to the position of the first element that compares greater than the
   * given value, then this function need not perform a search for the insert position. If
   * the given hint does not point to such a value, then the insert position is determined
   * by a binary search.
   *
   * If this set already contains a value that is equivalent to the given value, nothing
   * happens.
   *
   * Postcondition: this set contains a value equivalent to the given value and its size
   * has increased by one if the given value could be inserted
   *
   * @param hint an iterator pointing to the first element of this set that is greater
   * than the given value, or the end iterator if no such value exists
   * @param value the value to insert
   * @return an iterator pointing to the inserted value, or to the value that prevented
   * insertion
   */
  iterator insert(const_iterator hint, const value_type& value)
  {
    const auto result = do_insert(hint, value).first;
    assert(check_invariant());
    return result;
  }

  /**
   * Inserts the given value using the given hint to speed up insertion. If the given hint
   * points to the position of the first element that compares greater than the given
   * value, then this function need not perform a search for the insert position. If the
   * given hint does not point to such a value, then the insert position is determined by
   * a binary search.
   *
   * If this set already contains a value that is equivalent to the given value, nothing
   * happens. If the value could be inserted, it will have been moved into this set.
   *
   * Postcondition: this set contains a value equivalent to the given value and its size
   * has increased by one if the given value could be inserted.

   * @param hint an iterator pointing to the first element of this set that is greater
   * than the given value, or the end iterator if no such value exists
   * @param value the value to insert
   * @return an iterator pointing to the inserted value, or to the value that prevented
   * insertion
   */
  iterator insert(const_iterator hint, value_type&& value)
  {
    const auto result = do_insert(hint, std::move(value)).first;
    assert(check_invariant());
    return result;
  }

  /**
   * Inserts the values from the given range [first, last) into this set.
   *
   * Postcondition: for each value in the given range, this set contains an equivalent
   * value and its size has increased by one if the by the number of unique values in the
   * given range which were not present in this set
   *
   * @tparam I the iterator type
   * @param first the beginning of the range of values to insert
   * @param last the end of the range of values to insert (past-the-end iterator)
   */
  template <typename I>
  void insert(I first, I last)
  {
    while (first != last)
    {
      do_insert(*first);
      ++first;
    }
    assert(check_invariant());
  }

  /**
   * Inserts the values from the given range [first, last) into this set. The given count
   * can be used to avoid costly reallocations of the underlying vector. It should be at
   * least the number of unique items in the given range which are not yet present in this
   * set.
   *
   * Postcondition: for each value in the given range, this set contains an equivalent
   * value and its size has increased by one if the by the number of unique values in the
   * given range which were not present in this set
   *
   * @tparam I the iterator type
   * @param count the value by which to increase the underlying vector's capacity before
   * insertion
   * @param first the beginning of the range of values to insert
   * @param last the end of the range of values to insert (past-the-end iterator)
   */
  template <typename I>
  void insert(const size_type count, I first, I last)
  {
    m_data.reserve(size() + count);
    insert(first, last);
  }

  /**
   * Inserts the values from the given initializer list into this set.
   *
   * Postcondition: for each value in the given list, this set contains an equivalent
   * value and its size has increased by one if the by the number of unique values in the
   * given list which were not present in this set
   *
   * @param values the values to insert
   */
  void insert(std::initializer_list<value_type> values)
  {
    insert(values.size(), std::begin(values), std::end(values));
  }

  /**
   * Inserts a new value constructed from the given arguments into this set. If this set
   * already contains a value that is equivalent to the newly constructed value, the
   * constructed value is destroyed and otherwise nothing happens.
   *
   * If the constructed value could be inserted, then this function returns a pair of an
   * iterator to the inserted value and true, otherwise it returns a pair of an iterator
   * to the value that prevented insertion and false.
   *
   * The newly constructed value is not emplaced into the underlying vector; rather, it is
   * moved into it.
   *
   * Postcondition: this set contains a value equivalent to the given value and its size
   * has increased by one if the given value could be inserted
   *
   * @param args arguments with which to call the value's constructor
   * @return a pair of an iterator and a boolean that indicates whether the value was
   * inserted
   */
  template <typename... Args>
  std::pair<iterator, bool> emplace(Args&&... args)
  {
    return insert(value_type(std::forward<Args>(args)...));
  }

  /**
   * Inserts a new value constructed from the given arguments into this set, using the
   * given hint to speed up insertion. If the given hint points to the first element that
   * compares greater than the newly constructed value, then this function need not
   * perform a search for the insert position. If the given hint does not point to such a
   * value, then the insert position is determined by a binary search.
   *
   * If this set already contains a value that is equivalent to the newly constructed
   * value, the constructed value is destroyed and otherwise nothing happens.
   *
   * If the constructed value could be inserted, then this function returns a pair of an
   * iterator to the inserted value and true, otherwise it returns a pair of an iterator
   * to the value that prevented insertion and false.
   *
   * The newly constructed value is not emplaced into the underlying vector; rather, it is
   * moved into it.
   *
   * Postcondition: this set contains a value equivalent to the constructed value and its
   * size has increased by one if the value could be inserted
   *
   * @param hint insertion hint (an iterator pointing at the position before which the
   * value should be inserted)
   * @param args arguments with which to call the value's constructor
   * @return a pair of an iterator and a boolean that indicates whether the value was
   * inserted
   */
  template <typename... Args>
  iterator emplace_hint(const_iterator hint, Args&&... args)
  {
    return insert(hint, value_type(std::forward<Args>(args)...));
  }

  /**
   * Erases the value at the given position from this set. If the given position is not
   * valid in this set, then the behavior is undefined.
   *
   * Postcondition: the set does not contain the value that was previously at the given
   * position the size has decreased by one
   *
   * @param pos the position of the value to erase from this set
   */
  void erase(iterator pos)
  {
    m_data.erase(pos);
    assert(check_invariant());
  }

  /**
   * Erases the value at the given position from this set. If the given position is not
   * valid in this set, then the behavior is undefined.
   *
   * Postcondition: the set does not contain the value that was previously at the given
   * position the size has decreased by one.
   *
   * @param pos the position of the value to erase from this set
   */
  void erase(const_iterator pos)
  {
    m_data.erase(pos);
    assert(check_invariant());
  }

  /**
   * Erases all values in the given range [first, last) from this set. If the given range
   * is not valid for this set,  then the behavior is undefined.
   *
   * Postcondition: the set does not contain any of the values in the given range, and the
   * size has decreased by the length of the given range
   *
   * @param first the start of the range to erase
   * @param last the end of the range to erase (past-the-end iterator)
   * @return an iterator to the value following the last erased value
   */
  iterator erase(const_iterator first, const_iterator last)
  {
    const auto result = m_data.erase(first, last);
    assert(check_invariant());
    return result;
  }

  /**
   * Erases the values from this set which are equivalent to the given key.
   *
   * Postcondition: the set does not contain any value equivalent to the given key, and
   * the size has decreased accordingly
   *
   * @param key the key for the value to erase
   * @return the number of erased values
   */
  size_type erase(const key_type& key)
  {
    const auto size_before = size();
    auto [begin, end] = equal_range(key);
    erase(begin, end);
    return size_before - size();
  }

  /**
   * Swaps this set with the given set. This function is only callable if the underlying
   * collection is stored by value;
   *
   * @param other the set to swap with
   */
  void swap(set_adapter& other) noexcept
  {
    using std::swap;
    swap(m_data, other.m_data);
    assert(check_invariant());
  }

  /**
   * Finds the position of a value that is equivalent to the given key.
   *
   * @tparam K the key type
   * @param x the key
   * @return an iterator to a value that is equivalent to the given key, or end() if no
   * such value can be found
   */
  template <typename K>
  iterator find(const K& x)
  {
    auto it = lower_bound(x);
    return it != end() && is_equivalent(x, *it) ? it : end();
  }

  /**
   * Returns a range of values which are equivalent to the given key.
   *
   * @tparam K the key type
   * @param x the key
   * @return a maximal range of equivalent values in this set
   */
  template <typename K>
  std::pair<iterator, iterator> equal_range(const K& x)
  {
    return {lower_bound(x), upper_bound(x)};
  }

  /**
   * Returns the position of the greatest value that is less than or equal to the given
   * key, or end() if no such value can be found.
   *
   * @tparam K the key type
   * @param x the key
   * @return the position
   */
  template <typename K>
  iterator lower_bound(const K& x)
  {
    return std::lower_bound(std::begin(m_data), std::end(m_data), x, key_comp());
  }

  /**
   * Returns the position of the smallest value that is greater than the given key, or
   * end() if no such value can be found.
   *
   * @tparam K the key type
   * @param x the key
   * @return the position
   */
  template <typename K>
  iterator upper_bound(const K& x)
  {
    return std::upper_bound(std::begin(m_data), std::end(m_data), x, key_comp());
  }

  /**
   * Returns a reference to the underlying vector.
   */
  const auto& data() const { return m_data; }

  /**
   * Returns the underlying vector. Afterwards, this set will be empty.
   */
  auto release_data()
  {
    using CC = std::remove_reference_t<C>;
    return CC(std::move(m_data));
  }

protected:
  using base::check_invariant;
  using base::is_equivalent;

private:
  template <typename TT>
  std::pair<iterator, bool> do_insert(TT&& value)
  {
    const auto hint = insert_hint(value);
    return do_insert(hint, std::forward<TT>(value));
  }

  template <typename TT>
  std::pair<iterator, bool> do_insert(const_iterator hint, TT&& value)
  {
    const auto pos = hint != begin() ? std::prev(hint) : hint;
    if (!empty() && is_equivalent(value, *pos))
    {
      const auto offset = std::distance(cbegin(), pos);
      return {std::next(begin(), offset), false};
    }
    else
    {
      hint = insert_hint(hint, value);
      return {m_data.insert(hint, std::forward<TT>(value)), true};
    }
  }

  const_iterator insert_hint(const_iterator hint, const value_type& value) const
  {
    // correct the hint if necessary
    if (hint != end() && !key_comp()(value, *hint))
    {
      return insert_hint(value);
    }

    if (hint != begin())
    {
      const auto pos = std::prev(hint);
      if (!key_comp()(*pos, value))
      {
        return insert_hint(value);
      }
    }

    return hint;
  }

  const_iterator insert_hint(const value_type& value) const { return upper_bound(value); }
};

/**
 * Adapts the given collection to the read only interface of std::set. The given
 * collection is expected to be sorted and it must not contain any pair of two values
 * which are equivalent according to the comparator used.
 *
 * It must be ensured that the lifetime of returned adapter does not exceed the lifetime
 * of the given collection.
 *
 * @param data the collection
 * @param cmp the comparator
 * @return a set adapter using the given collection as its underlying collection
 */
template <typename C, typename Compare = std::less<typename C::value_type>>
const_set_adapter<const C&, Compare> wrap_set(
  const C& data, const Compare& cmp = Compare{})
{
  return const_set_adapter<const C&, Compare>(data, cmp);
}

/**
 * Adapts the given collection to the full interface of std::set. The given collection is
 * expected to be sorted and it must not contain any pair of two values which are
 * equivalent according to the comparator used.
 *
 * It must be ensured that the lifetime of returned adapter does not exceed the lifetime
 * of the given collection.
 *
 * @param data the collection
 * @param cmp the comparator
 * @return a set adapter using the given collection as its underlying collection
 */
template <typename C, typename Compare = std::less<typename C::value_type>>
set_adapter<C&, Compare> wrap_set(C& data, const Compare& cmp = Compare{})
{
  return set_adapter<C&, Compare>(data, cmp);
}

/**
 * Adapts the given collection to the full interface of std::set. The given collection
 * will be sorted and its elements made unique, that is, consecutive elements which are
 * equivalent according to the given comparator will be discarded.
 *
 * It must be ensured that the lifetime of returned adapter does not exceed the lifetime
 * of the given collection.
 *
 * @param data the collection
 * @param cmp the comparator
 * @return a set adapter using the given collection as its underlying collection
 */
template <typename C, typename Compare = std::less<typename C::value_type>>
set_adapter<C, Compare> create_set(C data, const Compare& cmp = Compare{})
{
  detail::sort_unique(data, cmp);
  return set_adapter<C, Compare>(std::move(data), cmp);
}

} // namespace kdl
